#include <vector>

using namespace std;

class Solution {
    int binary_search(vector<int>& nums, int left, int right, int& target) {
        if (left >= right) {
            return nums[left] == target ? left : -1;
        }
        if (nums[left] < nums[right]) {
            if (target < nums[left] || target > nums[right]) {
                return -1;
            }
        }
        int middle = (left + right) / 2;
        int ans1 = binary_search(nums, left, middle, target);
        int ans2 = binary_search(nums, middle + 1, right, target);
        if (ans1 != -1) {
            return ans1;
        }
        return ans2;
    }
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return -1;
        }
        return binary_search(nums, 0, nums.size() - 1, target);
    }
};